/**
 * 队列
1. 用链表实现链队列，支持 enqueue、dequeue、front、rear、isEmpty。
测试用例：enqueue(1,2,3)→front ()=1，rear ()=3→dequeue ()=1→队列剩 [2,3]。
2. 用两个栈实现队列功能（入队→栈 A，出队→栈 B），
测试用例：入队 1→2→3→出队= 1→入队 4→出队 = 2→出队 = 3→出队 = 4。
 */

/**
 * 1. 用链表实现链队列，支持 enqueue、dequeue、front、rear、isEmpty。
测试用例：enqueue(1,2,3)→front ()=1，rear ()=3→dequeue ()=1→队列剩 [2,3]。
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 队列节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 链队列结构体（包含头指针和尾指针）
typedef struct {
    Node* front;  // 队头指针（指向队头节点）
    Node* rear;   // 队尾指针（指向队尾节点）
} LinkedQueue;

// 初始化队列
LinkedQueue* createQueue() {
    LinkedQueue* queue = (LinkedQueue*)malloc(sizeof(LinkedQueue));
    if (queue == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    queue->front = queue->rear = NULL;  // 空队列时头尾指针均为NULL
    return queue;
}

// 检查队列是否为空
bool isEmpty(LinkedQueue* queue) {
    return queue->front == NULL;
}

// 入队操作
void enqueue(LinkedQueue* queue, int value) {
    // 创建新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;

    // 若队列为空，新节点既是队头也是队尾
    if (isEmpty(queue)) {
        queue->front = queue->rear = newNode;
    } else {
        // 否则添加到队尾
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

// 出队操作
int dequeue(LinkedQueue* queue) {
    if (isEmpty(queue)) {
        printf("错误：队列为空，无法出队\n");
        exit(1);
    }

    // 保存队头节点
    Node* temp = queue->front;
    int value = temp->data;

    // 更新队头指针
    queue->front = queue->front->next; 

    // 若队头指针为空，说明队列已空，队尾指针也置空
    if (queue->front == NULL) {
        queue->rear = NULL;
    }

    // 释放原队头节点内存
    free(temp);
    return value;
}

// 获取队头元素（不删除）
int front(LinkedQueue* queue) {
    if (isEmpty(queue)) {
        printf("错误：队列为空，无法获取队头元素\n");
        exit(1);
    }
    return queue->front->data;
}

// 获取队尾元素（不删除）
int rear(LinkedQueue* queue) {
    if (isEmpty(queue)) {
        printf("错误：队列为空，无法获取队尾元素\n");
        exit(1);
    }
    return queue->rear->data;
}

// 释放队列内存
void freeQueue(LinkedQueue* queue) {
    Node* current = queue->front;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    free(queue);
}

// 测试链队列
void testLinkedQueue() {
    LinkedQueue* queue = createQueue();
    
    // 入队 1, 2, 3
    enqueue(queue, 1);
    enqueue(queue, 2);
    enqueue(queue, 3);
    
    // 查看队头和队尾
    printf("front() = %d, rear() = %d\n", front(queue), rear(queue));  // 预期输出：1, 3
    
    // 出队
    printf("dequeue() = %d\n", dequeue(queue));  // 预期输出：1
    
    // 队列剩余元素
    printf("队列剩 [");
    if (!isEmpty(queue)) {
        Node* current = queue->front;
        while (current != NULL) {
            printf("%d", current->data);
            if (current->next != NULL) {
                printf(",");
            }
            current = current->next;
        }
    }
    printf("]\n");  // 预期输出：[2,3]
    
    freeQueue(queue);//!!!!!!!!!!!
}

// 主函数
int main() {
    printf("测试链队列：\n");
    testLinkedQueue();
    
    
    return 0;
}